package com.jinan.algorithm.opposingDoublePointers;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 两数之和
 * 给定一个整数数组numbers ,从数组中找出两个数满足相加之和等于目标数 target
 * 假设每个输入只对应唯一的答案,而且不可以重复使用相同的元素。
 * 返回两数的下标值,以数组形式返回
 */
public class TwoSum {
    public static void main(String[] args) {
        int[] numbers = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(numbers, target);
        System.out.println(Arrays.toString(result)); // 输出: [0, 1]
        System.out.println(Arrays.toString(twoPoint(numbers, target)));
    }
//    无序，哈希
    public static int[] twoSum(int[] numbers, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            if(map.containsKey(target - numbers[i])){
                return new int[]{map.get(target - numbers[i]), i};
            }else{
                map.put(numbers[i], i);
            }
        }
        return new int[]{-1, -1};
    }
// 有序 双指针
    public static int[] twoPoint(int[] numbers, int target) {
        int l=0,r=numbers.length-1;
        while(l<=r){
            int sum = numbers[l]+numbers[r];
            if (sum==target){
                return new int[]{l,r};
            }else if (sum<target){
                l++;
            }else if(sum>target){
                r--;
            }
        }
        return new int[]{-1,-1};
    }

}
